package com.example.javabasic.suanfa.jiandan.插入排序;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.List;

/**
 * @description 插入排序
 * @Author Lin FuYuan
 * @date 2021/5/8
 */
public class InsertSort {


    public static void main(String[] args) {
        int[] arr = {3,4,2,1,7,4,6,9,0,4,5,1,2,3,4,5,8};
        int[] sort = sort(arr);
        System.out.println(JSON.toJSONString(sort));
    }


    /**
     * 插入排序
     * @author Lin FuYuan
     * @param arr
     * @date 2021/5/8
     * @return int[]
     */
    public static int[] sort(int[] arr){
        //首先遍历
        for (int i = 0; i < arr.length; i++) {
            //判断第一个与第二个大小如果第二个大于第一个则跳过 如果小于则交换
            int n = i;
            while(n>=0 &&n < arr.length-1 && arr[n]>arr[n+1]){
                //交换
                int num = arr[n];
                arr[n] = arr[n+1];
                arr[n+1] = num;
                n--;
            }
        }
        return arr;
    }
}
